/*
 * com.future CO.,ltd.
 */
package com.future;

/**
 * Description:���ַ�����Ϊ���Ĵ������ٲ������
 * <p>
 * ����һ���ַ���?s?��ÿһ�β����㶼�������ַ���������λ�ò��������ַ���
 * <p>
 * ���㷵����?s?��Ϊ���Ĵ���?���ٲ�������?��
 * <p>
 * �����Ĵ����������ͷ�������ͬ���ַ�����
 * <p>
 * ?
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺s = "zzazz"
 * �����0
 * ���ͣ��ַ��� "zzazz" �Ѿ��ǻ��Ĵ��ˣ����Բ���Ҫ���κβ��������
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/minimum-insertion-steps-to-make-a-string-palindrome
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/4/3:23:24
 */
public class Solution_1312 {

    public static void main(String[] args) {
        String s = "zzazz";
        s = "mbadm";
        System.out.println(minInsertions(s));
    }

    /**
     * dp[i][j] ��ʾ���ȴ�i...j����ɻ�����С��Ҫ��ӵĻ��ĸ���
     * ��ô����dp[i][j]
     * ���1��dp[i][j-1]��ɻ��ĸ������٣��ڴ˻�����+1
     * eg:s=abc��Ҫ����dp[0][2],��Ϊ[0][1]=1(ab��Ҫ���һ���ַ��Ϳ��Գ�Ϊ����),��s�ĵ�һλ���һ���ַ�'c'����ʹ�ַ���s��Ϊ���ģ�����dp[0][2]=2
     * ���2���ȿ�dp[i+1][j]����ɻ��ĸ������٣��ڴ˻�����+1
     * eg:s=abc,dp[1][2]=1(bc��Ҫ���һ���ַ��Ϳ��Գ�Ϊ����)��Ȼ�����ַ���s��ĩβ������0λ�ַ���ȵ��ַ�a,����dp[0][2] = 2
     * ���3��s.charAt(i)�Ƿ���s.charAt(j)��ȣ������dp[i][j]=dp[i-1][j-1]
     * eg:s=abca,��dp[0][3]=dp[1][2]
     * <p>
     * dp[i][j] = min(���1�����2�����3)
     *
     * @param s
     * @return
     */
    public static int minInsertions(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        /**
         * dp[i][j] ��ʾ���ַ���λ��i��j����ɻ�����Ҫ������ٵ��ַ�����
         * ���ԣ�i<=j,ֻ��Ҫ��д���Ͻ�
         * �� i=jʱ�������ַ����ȶ���1������dp[i][i]=0�����ԽǶ�Ϊ0,
         */
        int[][] dp = new int[N][N];
        for (int i = 0; i < N - 1; i++) {
            /**
             * ����Ϊ2
             */
            dp[i][i + 1] = str[i] == str[i + 1] ? 0 : 1;
        }
        /**
         * �������ϣ��������Ҽ���
         * �ɲο�ͼCode01_MinimumInsertionStepsToMakeAStringPalindrome_3.jpg
         * ��dp[i][j]���ڱ�dp�õ�(i,j)���������(i-1,j),�±�����(i,j-1)����Сֵ����1�����3
         * �������������Сֵ
         */
        for (int i = N - 3; i >= 0; i--) {
            for (int j = i + 2; j < N; j++) {
                /**
                 * ���1��dp[i][j-1]��ɻ��ĸ������٣��ڴ˻�����+1
                 * eg:s=abc��Ҫ����dp[0][2],��Ϊ[0][1]=1(ab��Ҫ���һ���ַ��Ϳ��Գ�Ϊ����),
                 * ��s�ĵ�һλ���һ���ַ�'c'����ʹ�ַ���s��Ϊ���ģ�����dp[0][2]=2
                 *
                 * ���2���ȿ�dp[i+1][j]����ɻ��ĸ������٣��ڴ˻�����+1
                 * eg:s=abc,dp[1][2]=1(bc��Ҫ���һ���ַ��Ϳ��Գ�Ϊ����)��Ȼ�����ַ���s��ĩβ������0λ�ַ���ȵ��ַ�a,����dp[0][2] = 2
                 *
                 */
                dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;
                if (str[i] == str[j]) {
                    /**
                     * ���3��s.charAt(i)�Ƿ���s.charAt(j)��ȣ������dp[i][j]=dp[i-1][j-1]
                     * eg:s=abca,��dp[0][3]=dp[1][2]
                     */
                    dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
                }
            }
        }
        return dp[0][N - 1];
    }
}
